<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>Voro++: voro++.hh Source File</title>

<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css" />



</head>
<body>
<div id="top"><!-- do not remove this div! -->


<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  
  
  <td style="padding-left: 0.5em;">
   <div id="projectname">Voro++
   
   </div>
   
  </td>
  
  
  
 </tr>
 </tbody>
</table>
</div>

<!-- Generated by Doxygen 1.7.5.1 -->
<script type="text/javascript" src="dynsections.js"></script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="files.html"><span>File&#160;List</span></a></li>
      <li><a href="globals.html"><span>Globals</span></a></li>
    </ul>
  </div>
<div class="header">
  <div class="headertitle">
<div class="title">voro++.hh</div>  </div>
</div>
<div class="contents">
<a href="voro_09_09_8hh.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">// Voro++, a 3D cell-based Voronoi library</span>
<a name="l00002"></a>00002 <span class="comment">//</span>
<a name="l00003"></a>00003 <span class="comment">// Author   : Chris H. Rycroft (LBL / UC Berkeley)</span>
<a name="l00004"></a>00004 <span class="comment">// Email    : chr@alum.mit.edu</span>
<a name="l00005"></a>00005 <span class="comment">// Date     : August 30th 2011</span>
<a name="l00006"></a>00006 <span class="comment"></span>
<a name="l00007"></a>00007 <span class="comment">/** \file voro++.hh</span>
<a name="l00008"></a>00008 <span class="comment"> * \brief A file that loads all of the Voro++ header files. */</span>
<a name="l00009"></a>00009 <span class="comment"></span>
<a name="l00010"></a>00010 <span class="comment">/** \mainpage Voro++ class reference manual</span>
<a name="l00011"></a>00011 <span class="comment"> * \section intro Introduction</span>
<a name="l00012"></a>00012 <span class="comment"> * Voro++ is a software library for carrying out three-dimensional computations</span>
<a name="l00013"></a>00013 <span class="comment"> * of the Voronoi tessellation. A distinguishing feature of the Voro++ library</span>
<a name="l00014"></a>00014 <span class="comment"> * is that it carries out cell-based calculations, computing the Voronoi cell</span>
<a name="l00015"></a>00015 <span class="comment"> * for each particle individually, rather than computing the Voronoi</span>
<a name="l00016"></a>00016 <span class="comment"> * tessellation as a global network of vertices and edges. It is particularly</span>
<a name="l00017"></a>00017 <span class="comment"> * well-suited for applications that rely on cell-based statistics, where</span>
<a name="l00018"></a>00018 <span class="comment"> * features of Voronoi cells (eg. volume, centroid, number of faces) can be</span>
<a name="l00019"></a>00019 <span class="comment"> * used to analyze a system of particles.</span>
<a name="l00020"></a>00020 <span class="comment"> *</span>
<a name="l00021"></a>00021 <span class="comment"> * Voro++ is written in C++ and can be built as a static library that can be</span>
<a name="l00022"></a>00022 <span class="comment"> * linked to. This manual provides a reference for every function in the class</span>
<a name="l00023"></a>00023 <span class="comment"> * structure. For a general overview of the program, see the Voro++ website at</span>
<a name="l00024"></a>00024 <span class="comment"> * http://math.lbl.gov/voro++/ and in particular the example programs at</span>
<a name="l00025"></a>00025 <span class="comment"> * http://math.lbl.gov/voro++/examples/ that demonstrate many of the library&#39;s</span>
<a name="l00026"></a>00026 <span class="comment"> * features.</span>
<a name="l00027"></a>00027 <span class="comment"> *</span>
<a name="l00028"></a>00028 <span class="comment"> * \section class C++ class structure</span>
<a name="l00029"></a>00029 <span class="comment"> * The code is structured around several C++ classes. The voronoicell_base</span>
<a name="l00030"></a>00030 <span class="comment"> * class contains all of the routines for constructing a single Voronoi cell.</span>
<a name="l00031"></a>00031 <span class="comment"> * It represents the cell as a collection of vertices that are connected by</span>
<a name="l00032"></a>00032 <span class="comment"> * edges, and there are routines for initializing, making, and outputting the</span>
<a name="l00033"></a>00033 <span class="comment"> * cell. The voronoicell_base class form the base of the voronoicell and</span>
<a name="l00034"></a>00034 <span class="comment"> * voronoicell_neighbor classes, which add specialized routines depending on</span>
<a name="l00035"></a>00035 <span class="comment"> * whether neighboring particle ID information for each face must be tracked or</span>
<a name="l00036"></a>00036 <span class="comment"> * not. Collectively, these classes are referred to as &quot;voronoicell classes&quot;</span>
<a name="l00037"></a>00037 <span class="comment"> * within the documentation.</span>
<a name="l00038"></a>00038 <span class="comment"> *</span>
<a name="l00039"></a>00039 <span class="comment"> * There is a hierarchy of classes that represent three-dimensional particle</span>
<a name="l00040"></a>00040 <span class="comment"> * systems. All of these are derived from the voro_base class, which contains</span>
<a name="l00041"></a>00041 <span class="comment"> * constants that divide a three-dimensional system into a rectangular grid of</span>
<a name="l00042"></a>00042 <span class="comment"> * equally-sized rectangular blocks; this grid is used for computational</span>
<a name="l00043"></a>00043 <span class="comment"> * efficiency during the Voronoi calculations.</span>
<a name="l00044"></a>00044 <span class="comment"> *</span>
<a name="l00045"></a>00045 <span class="comment"> * The container_base, container, and container_poly are then derived from the</span>
<a name="l00046"></a>00046 <span class="comment"> * voro_base class to represent a particle system in a specific</span>
<a name="l00047"></a>00047 <span class="comment"> * three-dimensional rectangular box using both periodic and non-periodic</span>
<a name="l00048"></a>00048 <span class="comment"> * boundary conditions. In addition, the container_periodic_base,</span>
<a name="l00049"></a>00049 <span class="comment"> * container_periodic, and container_periodic_poly classes represent</span>
<a name="l00050"></a>00050 <span class="comment"> * a particle system in a three-dimensional non-orthogonal periodic domain,</span>
<a name="l00051"></a>00051 <span class="comment"> * defined by three periodicity vectors that represent a parallelepiped.</span>
<a name="l00052"></a>00052 <span class="comment"> * Collectively, these classes are referred to as &quot;container classes&quot; within</span>
<a name="l00053"></a>00053 <span class="comment"> * the documentation.</span>
<a name="l00054"></a>00054 <span class="comment"> *</span>
<a name="l00055"></a>00055 <span class="comment"> * The voro_compute template encapsulates all of the routines for computing</span>
<a name="l00056"></a>00056 <span class="comment"> * Voronoi cells. Each container class has a voro_compute template within</span>
<a name="l00057"></a>00057 <span class="comment"> * it, that accesses the container&#39;s particle system, and computes the Voronoi</span>
<a name="l00058"></a>00058 <span class="comment"> * cells.</span>
<a name="l00059"></a>00059 <span class="comment"> *</span>
<a name="l00060"></a>00060 <span class="comment"> * There are several wall classes that can be used to apply certain boundary</span>
<a name="l00061"></a>00061 <span class="comment"> * conditions using additional plane cuts during the Voronoi cell compution.</span>
<a name="l00062"></a>00062 <span class="comment"> * The code also contains a number of small loop classes, c_loop_all,</span>
<a name="l00063"></a>00063 <span class="comment"> * c_loop_subset, c_loop_all_periodic, and c_loop_order that can be used to</span>
<a name="l00064"></a>00064 <span class="comment"> * iterate over a certain subset of particles in a container. The latter class</span>
<a name="l00065"></a>00065 <span class="comment"> * makes use of a special particle_order class that stores a specific order of</span>
<a name="l00066"></a>00066 <span class="comment"> * particles within the container. The library also contains the classes</span>
<a name="l00067"></a>00067 <span class="comment"> * pre_container_base, pre_container, and pre_container_poly, that can be used</span>
<a name="l00068"></a>00068 <span class="comment"> * as temporary storage when importing data of unknown size.</span>
<a name="l00069"></a>00069 <span class="comment"> *</span>
<a name="l00070"></a>00070 <span class="comment"> * \section voronoicell The voronoicell classes</span>
<a name="l00071"></a>00071 <span class="comment"> * The voronoicell class represents a single Voronoi cell as a convex</span>
<a name="l00072"></a>00072 <span class="comment"> * polyhedron, with a set of vertices that are connected by edges. The class</span>
<a name="l00073"></a>00073 <span class="comment"> * contains a variety of functions that can be used to compute and output the</span>
<a name="l00074"></a>00074 <span class="comment"> * Voronoi cell corresponding to a particular particle. The command init()</span>
<a name="l00075"></a>00075 <span class="comment"> * can be used to initialize a cell as a large rectangular box. The Voronoi cell</span>
<a name="l00076"></a>00076 <span class="comment"> * can then be computed by repeatedly cutting it with planes that correspond to</span>
<a name="l00077"></a>00077 <span class="comment"> * the perpendicular bisectors between that particle and its neighbors.</span>
<a name="l00078"></a>00078 <span class="comment"> *</span>
<a name="l00079"></a>00079 <span class="comment"> * This is achieved by using the plane() routine, which will recompute the</span>
<a name="l00080"></a>00080 <span class="comment"> * cell&#39;s vertices and edges after cutting it with a single plane. This is the</span>
<a name="l00081"></a>00081 <span class="comment"> * key routine in voronoicell class. It begins by exploiting the convexity</span>
<a name="l00082"></a>00082 <span class="comment"> * of the underlying cell, tracing between edges to work out if the cell</span>
<a name="l00083"></a>00083 <span class="comment"> * intersects the cutting plane. If it does not intersect, then the routine</span>
<a name="l00084"></a>00084 <span class="comment"> * immediately exits. Otherwise, it finds an edge or vertex that intersects</span>
<a name="l00085"></a>00085 <span class="comment"> * the plane, and from there, traces out a new face on the cell, recomputing</span>
<a name="l00086"></a>00086 <span class="comment"> * the edge and vertex structure accordingly.</span>
<a name="l00087"></a>00087 <span class="comment"> *</span>
<a name="l00088"></a>00088 <span class="comment"> * Once the cell is computed, there are many routines for computing features of</span>
<a name="l00089"></a>00089 <span class="comment"> * the the Voronoi cell, such as its volume, surface area, or centroid. There</span>
<a name="l00090"></a>00090 <span class="comment"> * are also many routines for outputting features of the Voronoi cell, or</span>
<a name="l00091"></a>00091 <span class="comment"> * writing its shape in formats that can be read by Gnuplot or POV-Ray.</span>
<a name="l00092"></a>00092 <span class="comment"> *</span>
<a name="l00093"></a>00093 <span class="comment"> * \subsection internal Internal data representation</span>
<a name="l00094"></a>00094 <span class="comment"> * The voronoicell class has a public member p representing the</span>
<a name="l00095"></a>00095 <span class="comment"> * number of vertices. The polyhedral structure of the cell is stored</span>
<a name="l00096"></a>00096 <span class="comment"> * in the following arrays:</span>
<a name="l00097"></a>00097 <span class="comment"> *</span>
<a name="l00098"></a>00098 <span class="comment"> * - pts: a one-dimensional array of floating point numbers, that represent the</span>
<a name="l00099"></a>00099 <span class="comment"> *   position vectors x_0, x_1, ..., x_{p-1} of the polyhedron vertices.</span>
<a name="l00100"></a>00100 <span class="comment"> * - nu: the order of each vertex n_0, n_1, ..., n_{p-1}, corresponding to</span>
<a name="l00101"></a>00101 <span class="comment"> *   the number of other vertices to which each is connected.</span>
<a name="l00102"></a>00102 <span class="comment"> * - ed: a two-dimensional table of edges and relations. For the ith vertex,</span>
<a name="l00103"></a>00103 <span class="comment"> *   ed[i] has 2n_i+1 elements. The first n_i elements are the edges e(j,i),</span>
<a name="l00104"></a>00104 <span class="comment"> *   where e(j,i) is the jth neighbor of vertex i. The edges are ordered</span>
<a name="l00105"></a>00105 <span class="comment"> *   according to a right-hand rule with respect to an outward-pointing normal.</span>
<a name="l00106"></a>00106 <span class="comment"> *   The next n_i elements are the relations l(j,i) which satisfy the property</span>
<a name="l00107"></a>00107 <span class="comment"> *   e(l(j,i),e(j,i)) = i. The final element of the ed[i] list is a back</span>
<a name="l00108"></a>00108 <span class="comment"> *   pointer used in memory allocation.</span>
<a name="l00109"></a>00109 <span class="comment"> *</span>
<a name="l00110"></a>00110 <span class="comment"> * In a very large number of cases, the values of n_i will be 3. This is because</span>
<a name="l00111"></a>00111 <span class="comment"> * the only way that a higher-order vertex can be created in the plane()</span>
<a name="l00112"></a>00112 <span class="comment"> * routine is if the cutting plane perfectly intersects an existing vertex. For</span>
<a name="l00113"></a>00113 <span class="comment"> * random particle arrangements with position vectors specified to double</span>
<a name="l00114"></a>00114 <span class="comment"> * precision this should happen very rarely. A preliminary version of this code</span>
<a name="l00115"></a>00115 <span class="comment"> * was quite successful with only making use of vertices of order 3. However,</span>
<a name="l00116"></a>00116 <span class="comment"> * when calculating millions of cells, it was found that this approach is not</span>
<a name="l00117"></a>00117 <span class="comment"> * robust, since a single floating point error can invalidate the computation.</span>
<a name="l00118"></a>00118 <span class="comment"> * This can also be a problem for cases featuring crystalline arrangements of</span>
<a name="l00119"></a>00119 <span class="comment"> * particles where the corresponding Voronoi cells may have high-order vertices</span>
<a name="l00120"></a>00120 <span class="comment"> * by construction.</span>
<a name="l00121"></a>00121 <span class="comment"> *</span>
<a name="l00122"></a>00122 <span class="comment"> * Because of this, Voro++ takes the approach that it if an existing vertex is</span>
<a name="l00123"></a>00123 <span class="comment"> * within a small numerical tolerance of the cutting plane, it is treated as</span>
<a name="l00124"></a>00124 <span class="comment"> * being exactly on the plane, and the polyhedral topology is recomputed</span>
<a name="l00125"></a>00125 <span class="comment"> * accordingly. However, while this improves robustness, it also adds the</span>
<a name="l00126"></a>00126 <span class="comment"> * complexity that n_i may no longer always be 3. This causes memory management</span>
<a name="l00127"></a>00127 <span class="comment"> * to be significantly more complicated, as different vertices require a</span>
<a name="l00128"></a>00128 <span class="comment"> * different number of elements in the ed[][] array. To accommodate this, the</span>
<a name="l00129"></a>00129 <span class="comment"> * voronoicell class allocated edge memory in a different array called mep[][],</span>
<a name="l00130"></a>00130 <span class="comment"> * in such a way that all vertices of order k are held in mep[k]. If vertex</span>
<a name="l00131"></a>00131 <span class="comment"> * i has order k, then ed[i] points to memory within mep[k]. The array ed[][]</span>
<a name="l00132"></a>00132 <span class="comment"> * is never directly initialized as a two-dimensional array itself, but points</span>
<a name="l00133"></a>00133 <span class="comment"> * at allocations within mep[][]. To the user, it appears as though each row of</span>
<a name="l00134"></a>00134 <span class="comment"> * ed[][] has a different number of elements. When vertices are added or</span>
<a name="l00135"></a>00135 <span class="comment"> * deleted, care must be taken to reorder and reassign elements in these</span>
<a name="l00136"></a>00136 <span class="comment"> * arrays.</span>
<a name="l00137"></a>00137 <span class="comment"> *</span>
<a name="l00138"></a>00138 <span class="comment"> * During the plane() routine, the code traces around the vertices of the cell,</span>
<a name="l00139"></a>00139 <span class="comment"> * and adds new vertices along edges which intersect the cutting plane to</span>
<a name="l00140"></a>00140 <span class="comment"> * create a new face. The values of l(j,i) are used in this computation, as</span>
<a name="l00141"></a>00141 <span class="comment"> * when the code is traversing from one vertex on the cell to another, this</span>
<a name="l00142"></a>00142 <span class="comment"> * information allows the code to immediately work out which edge of a vertex</span>
<a name="l00143"></a>00143 <span class="comment"> * points back to the one it came from. As new vertices are created, the l(j,i)</span>
<a name="l00144"></a>00144 <span class="comment"> * are also updated to ensure consistency. To ensure robustness, the plane</span>
<a name="l00145"></a>00145 <span class="comment"> * cutting algorithm should work with any possible combination of vertices</span>
<a name="l00146"></a>00146 <span class="comment"> * which are inside, outside, or exactly on the cutting plane.</span>
<a name="l00147"></a>00147 <span class="comment"> *</span>
<a name="l00148"></a>00148 <span class="comment"> * Vertices exactly on the cutting plane create some additional computational</span>
<a name="l00149"></a>00149 <span class="comment"> * difficulties. If there are two marginal vertices connected by an existing</span>
<a name="l00150"></a>00150 <span class="comment"> * edge, then it would be possible for duplicate edges to be created between</span>
<a name="l00151"></a>00151 <span class="comment"> * those two vertices, if the plane routine traces along both sides of this</span>
<a name="l00152"></a>00152 <span class="comment"> * edge while constructing the new face. The code recognizes these cases and</span>
<a name="l00153"></a>00153 <span class="comment"> * prevents the double edge from being formed. Another possibility is the</span>
<a name="l00154"></a>00154 <span class="comment"> * formation of vertices of order two or one. At the end of the plane cutting</span>
<a name="l00155"></a>00155 <span class="comment"> * routine, the code checks to see if any of these are present, removing the</span>
<a name="l00156"></a>00156 <span class="comment"> * order one vertices by just deleting them, and removing the order two</span>
<a name="l00157"></a>00157 <span class="comment"> * vertices by connecting the two neighbors of each vertex together. It is</span>
<a name="l00158"></a>00158 <span class="comment"> * possible that the removal of a single low-order vertex could result in the</span>
<a name="l00159"></a>00159 <span class="comment"> * creation of additional low-order vertices, so the process is applied</span>
<a name="l00160"></a>00160 <span class="comment"> * recursively until no more are left.</span>
<a name="l00161"></a>00161 <span class="comment"> *</span>
<a name="l00162"></a>00162 <span class="comment"> * \section container The container classes</span>
<a name="l00163"></a>00163 <span class="comment"> * There are four container classes available for general usage: container,</span>
<a name="l00164"></a>00164 <span class="comment"> * container_poly, container_periodic, and container_periodic_poly. Each of</span>
<a name="l00165"></a>00165 <span class="comment"> * these represent a system of particles in a specific three-dimensional</span>
<a name="l00166"></a>00166 <span class="comment"> * geometry. They contain routines for importing particles from a text file,</span>
<a name="l00167"></a>00167 <span class="comment"> * and adding particles individually. They also contain a large number of</span>
<a name="l00168"></a>00168 <span class="comment"> * analyzing and outputting the particle system. Internally, the routines that</span>
<a name="l00169"></a>00169 <span class="comment"> * compute Voronoi cells do so by making use of the voro_compute template.</span>
<a name="l00170"></a>00170 <span class="comment"> * Each container class contains routines that tell the voro_compute template</span>
<a name="l00171"></a>00171 <span class="comment"> * about the specific geometry of this container.</span>
<a name="l00172"></a>00172 <span class="comment"> *</span>
<a name="l00173"></a>00173 <span class="comment"> * \section voro_compute The voro_compute template</span>
<a name="l00174"></a>00174 <span class="comment"> * The voro_compute template encapsulates the routines for carrying out the</span>
<a name="l00175"></a>00175 <span class="comment"> * Voronoi cell computations. It contains data structures suchs as a mask and a</span>
<a name="l00176"></a>00176 <span class="comment"> * queue that are used in the computations. The voro_compute template is</span>
<a name="l00177"></a>00177 <span class="comment"> * associated with a specific container class, and during the computation, it</span>
<a name="l00178"></a>00178 <span class="comment"> * calls routines in the container class to access the particle positions that</span>
<a name="l00179"></a>00179 <span class="comment"> * are stored there.</span>
<a name="l00180"></a>00180 <span class="comment"> *</span>
<a name="l00181"></a>00181 <span class="comment"> * The key routine in this class is compute_cell(), which makes use of a</span>
<a name="l00182"></a>00182 <span class="comment"> * voronoicell class to construct a Voronoi cell for a specific particle in the</span>
<a name="l00183"></a>00183 <span class="comment"> * container. The basic approach that this function takes is to repeatedly cut</span>
<a name="l00184"></a>00184 <span class="comment"> * the Voronoi cell by planes corresponding neighboring particles, and stop</span>
<a name="l00185"></a>00185 <span class="comment"> * when it recognizes that all the remaining particles in the container are too</span>
<a name="l00186"></a>00186 <span class="comment"> * far away to possibly influence cell&#39;s shape. The code makes use of two</span>
<a name="l00187"></a>00187 <span class="comment"> * possible methods for working out when a cell computation is complete:</span>
<a name="l00188"></a>00188 <span class="comment"> *</span>
<a name="l00189"></a>00189 <span class="comment"> * - Radius test: if the maximum distance of a Voronoi cell</span>
<a name="l00190"></a>00190 <span class="comment"> *   vertex from the cell center is R, then no particles more than a distance</span>
<a name="l00191"></a>00191 <span class="comment"> *   2R away can possibly influence the cell. This a very fast computation to</span>
<a name="l00192"></a>00192 <span class="comment"> *   do, but it has no directionality: if the cell extends a long way in one</span>
<a name="l00193"></a>00193 <span class="comment"> *   direction then particles a long distance in other directions will still</span>
<a name="l00194"></a>00194 <span class="comment"> *   need to be tested.</span>
<a name="l00195"></a>00195 <span class="comment"> * - Region test: it is possible to test whether a specific region can</span>
<a name="l00196"></a>00196 <span class="comment"> *   possibly influence the cell by applying a series of plane tests at the</span>
<a name="l00197"></a>00197 <span class="comment"> *   point on the region which is closest to the Voronoi cell center. This is a</span>
<a name="l00198"></a>00198 <span class="comment"> *   slower computation to do, but it has directionality.</span>
<a name="l00199"></a>00199 <span class="comment"> *</span>
<a name="l00200"></a>00200 <span class="comment"> * Another useful observation is that the regions that need to be tested are</span>
<a name="l00201"></a>00201 <span class="comment"> * simply connected, meaning that if a particular region does not need to be</span>
<a name="l00202"></a>00202 <span class="comment"> * tested, then neighboring regions which are further away do not need to be</span>
<a name="l00203"></a>00203 <span class="comment"> * tested.</span>
<a name="l00204"></a>00204 <span class="comment"> *</span>
<a name="l00205"></a>00205 <span class="comment"> * For maximum efficiency, it was found that a hybrid approach making use of</span>
<a name="l00206"></a>00206 <span class="comment"> * both of the above tests worked well in practice. Radius tests work well for</span>
<a name="l00207"></a>00207 <span class="comment"> * the first few blocks, but switching to region tests after then prevent the</span>
<a name="l00208"></a>00208 <span class="comment"> * code from becoming extremely slow, due to testing over very large spherical</span>
<a name="l00209"></a>00209 <span class="comment"> * shells of particles. The compute_cell() routine therefore takes the</span>
<a name="l00210"></a>00210 <span class="comment"> * following approach:</span>
<a name="l00211"></a>00211 <span class="comment"> *</span>
<a name="l00212"></a>00212 <span class="comment"> * - Initialize the voronoicell class to fill the entire computational domain.</span>
<a name="l00213"></a>00213 <span class="comment"> * - Cut the cell by any wall objects that have been added to the container.</span>
<a name="l00214"></a>00214 <span class="comment"> * - Apply plane cuts to the cell corresponding to the other particles which</span>
<a name="l00215"></a>00215 <span class="comment"> *   are within the current particle&#39;s region.</span>
<a name="l00216"></a>00216 <span class="comment"> * - Test over a pre-computed worklist of neighboring regions, that have been</span>
<a name="l00217"></a>00217 <span class="comment"> *   ordered according to the minimum distance away from the particle&#39;s</span>
<a name="l00218"></a>00218 <span class="comment"> *   position. Apply radius tests after every few regions to see if the</span>
<a name="l00219"></a>00219 <span class="comment"> *   calculation can terminate.</span>
<a name="l00220"></a>00220 <span class="comment"> * - If the code reaches the end of the worklist, add all the neighboring</span>
<a name="l00221"></a>00221 <span class="comment"> *   regions to a new list.</span>
<a name="l00222"></a>00222 <span class="comment"> * - Carry out a region test on the first item of the list. If the region needs</span>
<a name="l00223"></a>00223 <span class="comment"> *   to be tested, apply the plane() routine for all of its particles, and then</span>
<a name="l00224"></a>00224 <span class="comment"> *   add any neighboring regions to the end of the list that need to be tested.</span>
<a name="l00225"></a>00225 <span class="comment"> *   Continue until the list has no elements left.</span>
<a name="l00226"></a>00226 <span class="comment"> *</span>
<a name="l00227"></a>00227 <span class="comment"> * The compute_cell() routine forms the basis of many other routines, such as</span>
<a name="l00228"></a>00228 <span class="comment"> * store_cell_volumes() and draw_cells_gnuplot() that can be used to calculate</span>
<a name="l00229"></a>00229 <span class="comment"> * and draw the cells in a container.</span>
<a name="l00230"></a>00230 <span class="comment"> *</span>
<a name="l00231"></a>00231 <span class="comment"> * \section walls Wall computation</span>
<a name="l00232"></a>00232 <span class="comment"> * Wall computations are handled by making use of a pure virtual wall class.</span>
<a name="l00233"></a>00233 <span class="comment"> * Specific wall types are derived from this class, and require the</span>
<a name="l00234"></a>00234 <span class="comment"> * specification of two routines: point_inside() that tests to see if a point</span>
<a name="l00235"></a>00235 <span class="comment"> * is inside a wall or not, and cut_cell() that cuts a cell according to the</span>
<a name="l00236"></a>00236 <span class="comment"> * wall&#39;s position. The walls can be added to the container using the</span>
<a name="l00237"></a>00237 <span class="comment"> * add_wall() command, and these are called each time a compute_cell() command</span>
<a name="l00238"></a>00238 <span class="comment"> * is carried out. At present, wall types for planes, spheres, cylinders, and</span>
<a name="l00239"></a>00239 <span class="comment"> * cones are provided, although custom walls can be added by creating new</span>
<a name="l00240"></a>00240 <span class="comment"> * classes derived from the pure virtual class. Currently all wall types</span>
<a name="l00241"></a>00241 <span class="comment"> * approximate the wall surface with a single plane, which produces some small</span>
<a name="l00242"></a>00242 <span class="comment"> * errors, but generally gives good results for dense particle packings in</span>
<a name="l00243"></a>00243 <span class="comment"> * direct contact with a wall surface. It would be possible to create more</span>
<a name="l00244"></a>00244 <span class="comment"> * accurate walls by making cut_cell() routines that approximate the curved</span>
<a name="l00245"></a>00245 <span class="comment"> * surface with multiple plane cuts.</span>
<a name="l00246"></a>00246 <span class="comment"> *</span>
<a name="l00247"></a>00247 <span class="comment"> * The wall objects can used for periodic calculations, although to obtain</span>
<a name="l00248"></a>00248 <span class="comment"> * valid results, the walls should also be periodic as well. For example, in a</span>
<a name="l00249"></a>00249 <span class="comment"> * domain that is periodic in the x direction, a cylinder aligned along the x</span>
<a name="l00250"></a>00250 <span class="comment"> * axis could be added. At present, the interior of all wall objects are convex</span>
<a name="l00251"></a>00251 <span class="comment"> * domains, and consequently any superposition of them will be a convex domain</span>
<a name="l00252"></a>00252 <span class="comment"> * also. Carrying out computations in non-convex domains poses some problems,</span>
<a name="l00253"></a>00253 <span class="comment"> * since this could theoretically lead to non-convex Voronoi cells, which the</span>
<a name="l00254"></a>00254 <span class="comment"> * internal data representation of the voronoicell class does not support. For</span>
<a name="l00255"></a>00255 <span class="comment"> * non-convex cases where the wall surfaces feature just a small amount of</span>
<a name="l00256"></a>00256 <span class="comment"> * negative curvature (eg. a torus) approximating the curved surface with a</span>
<a name="l00257"></a>00257 <span class="comment"> * single plane cut may give an acceptable level of accuracy. For non-convex</span>
<a name="l00258"></a>00258 <span class="comment"> * cases that feature internal angles, the best strategy may be to decompose</span>
<a name="l00259"></a>00259 <span class="comment"> * the domain into several convex subdomains, carry out a calculation in each,</span>
<a name="l00260"></a>00260 <span class="comment"> * and then add the results together. The voronoicell class cannot be easily</span>
<a name="l00261"></a>00261 <span class="comment"> * modified to handle non-convex cells as this would fundamentally alter the</span>
<a name="l00262"></a>00262 <span class="comment"> * algorithms that it uses, and cases could arise where a single plane cut</span>
<a name="l00263"></a>00263 <span class="comment"> * could create several new faces as opposed to just one.</span>
<a name="l00264"></a>00264 <span class="comment"> *</span>
<a name="l00265"></a>00265 <span class="comment"> * \section loops Loop classes</span>
<a name="l00266"></a>00266 <span class="comment"> * The container classes have a number of simple routines for calculating</span>
<a name="l00267"></a>00267 <span class="comment"> * Voronoi cells for all particles within them. However, in some situations it</span>
<a name="l00268"></a>00268 <span class="comment"> * is desirable to iterate over a specific subset of particles. This can be</span>
<a name="l00269"></a>00269 <span class="comment"> * achieved with the c_loop classes that are all derived from the c_loop_base</span>
<a name="l00270"></a>00270 <span class="comment"> * class. Each class can iterate over a specific subset of particles in a</span>
<a name="l00271"></a>00271 <span class="comment"> * container. There are three loop classes for use with the container and</span>
<a name="l00272"></a>00272 <span class="comment"> * container_poly classes:</span>
<a name="l00273"></a>00273 <span class="comment"> *</span>
<a name="l00274"></a>00274 <span class="comment"> * - c_loop_all will loop over all of the particles in a container.</span>
<a name="l00275"></a>00275 <span class="comment"> * - c_loop_subset will loop over a subset of particles in a container that lie</span>
<a name="l00276"></a>00276 <span class="comment"> *   within some geometrical region. It can loop over particles in a</span>
<a name="l00277"></a>00277 <span class="comment"> *   rectangular box, particles in a sphere, or particles that lie within</span>
<a name="l00278"></a>00278 <span class="comment"> *   specific internal computational blocks.</span>
<a name="l00279"></a>00279 <span class="comment"> * - c_loop_order will loop over a specific list of particles that were</span>
<a name="l00280"></a>00280 <span class="comment"> *   previously stored in a particle_order class.</span>
<a name="l00281"></a>00281 <span class="comment"> *</span>
<a name="l00282"></a>00282 <span class="comment"> * Several of the key routines within the container classes (such as</span>
<a name="l00283"></a>00283 <span class="comment"> * draw_cells_gnuplot and print_custom) have versions where they can be passed</span>
<a name="l00284"></a>00284 <span class="comment"> * a loop class to use. Loop classes can also be used directly and there are</span>
<a name="l00285"></a>00285 <span class="comment"> * some examples on the library website that demonstrate this. It is also</span>
<a name="l00286"></a>00286 <span class="comment"> * possible to write custom loop classes.</span>
<a name="l00287"></a>00287 <span class="comment"> *</span>
<a name="l00288"></a>00288 <span class="comment"> * In addition to the loop classes mentioned above, there is also a</span>
<a name="l00289"></a>00289 <span class="comment"> * c_loop_all_periodic class, that is specifically for use with the</span>
<a name="l00290"></a>00290 <span class="comment"> * container_periodic and container_periodic_poly classes. Since the data</span>
<a name="l00291"></a>00291 <span class="comment"> * structures of these containers differ considerably, it requires a different</span>
<a name="l00292"></a>00292 <span class="comment"> * loop class that is not interoperable with the others.</span>
<a name="l00293"></a>00293 <span class="comment"> *</span>
<a name="l00294"></a>00294 <span class="comment"> * \section pre_container The pre_container classes</span>
<a name="l00295"></a>00295 <span class="comment"> * Voro++ makes use of internal computational grid of blocks that are used to</span>
<a name="l00296"></a>00296 <span class="comment"> * configure the code for maximum efficiency. As discussed on the library</span>
<a name="l00297"></a>00297 <span class="comment"> * website, the best performance is achieved for around 5 particles per block,</span>
<a name="l00298"></a>00298 <span class="comment"> * with anything in the range from 3 to 12 giving good performance. Usually</span>
<a name="l00299"></a>00299 <span class="comment"> * the size of the grid can be chosen by ensuring that the number of blocks is</span>
<a name="l00300"></a>00300 <span class="comment"> * equal to the number of particles divided by 5.</span>
<a name="l00301"></a>00301 <span class="comment"> *</span>
<a name="l00302"></a>00302 <span class="comment"> * However, this can be difficult to choose in cases when the number of</span>
<a name="l00303"></a>00303 <span class="comment"> * particles is not known a priori, and in thes cases the pre_container classes</span>
<a name="l00304"></a>00304 <span class="comment"> * can be used. They can import an arbitrary number of particle positions from</span>
<a name="l00305"></a>00305 <span class="comment"> * a file, dynamically allocating memory in chunks as necessary. Once particles</span>
<a name="l00306"></a>00306 <span class="comment"> * are imported, they can guess an optimal block arrangement to use for the</span>
<a name="l00307"></a>00307 <span class="comment"> * container class, and then transfer the particles to the container. By</span>
<a name="l00308"></a>00308 <span class="comment"> * default, this procedure is used by the command-line utility to enable it to</span>
<a name="l00309"></a>00309 <span class="comment"> * work well with arbitrary sizes of input data.</span>
<a name="l00310"></a>00310 <span class="comment"> *</span>
<a name="l00311"></a>00311 <span class="comment"> * The pre_container class can be used when no particle radius information is</span>
<a name="l00312"></a>00312 <span class="comment"> * available, and the pre_container_poly class can be used when radius</span>
<a name="l00313"></a>00313 <span class="comment"> * information is available. At present, the pre_container classes can only be</span>
<a name="l00314"></a>00314 <span class="comment"> * used with the container and container_poly classes. They do not support</span>
<a name="l00315"></a>00315 <span class="comment"> * the container_periodic and container_periodic_poly classes. */</span>
<a name="l00316"></a>00316 
<a name="l00317"></a>00317 <span class="preprocessor">#ifndef VOROPP_HH</span>
<a name="l00318"></a>00318 <span class="preprocessor"></span><span class="preprocessor">#define VOROPP_HH</span>
<a name="l00319"></a>00319 <span class="preprocessor"></span>
<a name="l00320"></a>00320 <span class="preprocessor">#include &quot;<a class="code" href="config_8hh.html" title="Master configuration file for setting various compile-time options.">config.hh</a>&quot;</span>
<a name="l00321"></a>00321 <span class="preprocessor">#include &quot;<a class="code" href="common_8hh.html" title="Header file for the small helper functions.">common.hh</a>&quot;</span>
<a name="l00322"></a>00322 <span class="preprocessor">#include &quot;<a class="code" href="cell_8hh.html" title="Header file for the voronoicell and related classes.">cell.hh</a>&quot;</span>
<a name="l00323"></a>00323 <span class="preprocessor">#include &quot;<a class="code" href="v__base_8hh.html" title="Header file for the base Voronoi container class.">v_base.hh</a>&quot;</span>
<a name="l00324"></a>00324 <span class="preprocessor">#include &quot;<a class="code" href="container_8hh.html" title="Header file for the container_base and related classes.">container.hh</a>&quot;</span>
<a name="l00325"></a>00325 <span class="preprocessor">#include &quot;<a class="code" href="unitcell_8hh.html" title="Header file for the unitcell class.">unitcell.hh</a>&quot;</span>
<a name="l00326"></a>00326 <span class="preprocessor">#include &quot;<a class="code" href="container__prd_8hh.html" title="Header file for the container_periodic_base and related classes.">container_prd.hh</a>&quot;</span>
<a name="l00327"></a>00327 <span class="preprocessor">#include &quot;<a class="code" href="pre__container_8hh.html" title="Header file for the pre_container and related classes.">pre_container.hh</a>&quot;</span>
<a name="l00328"></a>00328 <span class="preprocessor">#include &quot;<a class="code" href="v__compute_8hh.html" title="Header file for the voro_compute template and related classes.">v_compute.hh</a>&quot;</span>
<a name="l00329"></a>00329 <span class="preprocessor">#include &quot;<a class="code" href="c__loops_8hh.html" title="Header file for the loop classes.">c_loops.hh</a>&quot;</span>
<a name="l00330"></a>00330 <span class="preprocessor">#include &quot;<a class="code" href="wall_8hh.html" title="Header file for the derived wall classes.">wall.hh</a>&quot;</span>
<a name="l00331"></a>00331 
<a name="l00332"></a>00332 <span class="preprocessor">#endif</span>
</pre></div></div>
</div>


<hr class="footer"/><address class="footer"><small>
Generated on Fri Sep 23 2011 22:49:06 for Voro++ by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.7.5.1
</small></address>

</body>
</html>
